/*
 *  author: lichuang
 *  2010-09-24
 */

#include "heap.h"
#include "common/common.h"
#include "common/array.h"

static void maxheap_heapify(int array[], int i, int n);
static void build_maxheap(int array[], int n);
static void maxheap_heapify_norecursion(int array[], int i, int n);
static void build_maxheap_norecursion(int array[], int n);

static int parent(int i) {
  return i / 2;
}

static int lchild(int i, int size) {
  int result = 2 * i + 1;
  return result < size ? result : -1;
}

static int rchild(int i, int size) {
  int result = 2 * i + 2;
  return result < size ? result : -1;
}

void maxheap_heapify(int array[], int i, int size) {
  int left = lchild(i, size);
  int right = rchild(i, size);
  int largest = i;

  if (left != -1 && array[i] < array[left]) {
    largest = left;
  }
  if (right != -1 && array[largest] < array[right]) {
    largest = right;
  }
  if (largest != i) {
    exchange(&array[largest], &array[i]);
    maxheap_heapify(array, largest, size);
  }
}

void build_maxheap(int array[], int size) {
  int i;

  for (i = size / 2 + 1; i >= 0; --i) {
    maxheap_heapify(array, i, size);
  }
}

void maxheap_sort_impl(int array[], int size) {
  int i;
  build_maxheap(array, size);
  for (i = size - 1; i >= 1; --i) {
    exchange(&array[i], &array[0]);
    maxheap_heapify(array, 0, i);
  }
}

void maxheap_sort(array_t *array) {
  maxheap_sort_impl(array->data, array->size);
}

void maxheap_heapify_norecursion(int array[], int i, int size) {
  int left, right;
  int largest = i;

  while (largest < size) {
    left = lchild(i, size);
    right = rchild(i, size);
    if (left != -1 && array[i] < array[left]) {
      largest = left;
    }
    if (right != -1 && array[largest] < array[right]) {
      largest = right;
    }
    if (largest != i) {
      exchange(&array[largest], &array[i]);
      i = largest;
    } else {
      break;
    }
  }
}

void build_maxheap_norecursion(int array[], int size) {
  int i;

  for (i = size / 2 + 1; i >= 0; --i) {
    maxheap_heapify_norecursion(array, i, size);
  }
}

void maxheap_sort_norecursion_impl(int array[], int size) {
  int i;
  build_maxheap_norecursion(array, size);
  for (i = size - 1; i >= 1; --i) {
    exchange(&array[i], &array[0]);
    maxheap_heapify_norecursion(array, 0, i);
  }
}

void maxheap_sort_norecursion(array_t *array) {
  maxheap_sort_norecursion_impl(array->data, array->size);
}

int  maxheap_maximum(const array_t *array) {
  return array->data[0];
}

int  maxheap_extract_max(array_t* array) {
  int *p = array->data;
  int size = array->size;
  int max = p[0];
  p[0] = p[size - 1];
  maxheap_heapify(p, 0, size -1);
  return max;
}

void maxheap_increase_key(array_t *array, int i, int key) {
  int *p = array->data;
  if (key < p[i]) {
    printf("error: new key is smaller than the old key\n");
    return;
  }
  p[i] = key;
  int next;
  while (i >= 0) {
    next = parent(i);
    if (p[i] > p[next]) {
      exchange(&p[i], &p[next]);
      i = next;
    } else {
      break;
    }
  }
}

void maxheap_insert(array_t *array, int key) {
  array = array_resize(array, array->size + 1);
  maxheap_increase_key(array, array->size, key);
}

